package com.ljy.my_study.lintcode.最大权值的路径;
/** 
* @author James
* @date 2018年4月22日 
*/
public class MaxWeightMain {
	public int maxWeight(int[][] nums) {
		if(nums==null) {
			return 0;
		}
		if(nums.length==0) {
			return 0;
		}
		if(nums[0].length==0) {
			return 0;
		}
		
		int n=nums.length;
		int m=nums[n-1].length;
		return maxWeight(nums,n,m);
	}
	
	public int maxWeight(int[][] nums,int n,int m) {
		if(nums==null) {
			return 0;
		}
		if(n<0) {
			return 0;
		}
		if(m<0) {
			return 0;
		}
		
        int i=n;
        int j=m;
        int maxWeight=nums[i][j];
        while(i-1>0||j-1>0) {
        	int left=0;
            int down=0;
            if(i-1>=0){
                left=nums[i-1][j];
            }
            if(j-1>=0){
                down=nums[i][j-1];
            }
            if(left>down) {
            	maxWeight+=left;
            	i--;
            }else if(left<down) {
            	maxWeight+=down;
            	j--;
            }else {
            	int nextI=i;
            	int nextJ=j;
            	int leftNextMaxWeight=maxWeight(nums,nextI-1,nextJ);
            	int downNextMaxWeight=maxWeight(nums,nextI,nextJ-1);
            	if(leftNextMaxWeight>=downNextMaxWeight) {
            		maxWeight+=left;
            		i--;
            	}else if(leftNextMaxWeight<downNextMaxWeight) {
            		maxWeight+=down;
            		j--;
            	}
            }
        }
        return maxWeight;
	}
}
